#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
//打家劫舍②：https://leetcode.cn/problems/house-robber-ii/description/
using namespace std;
class Solution {
public:
    //1.状态表示： f[i]: 到i位置且偷，取得的最大金额
    //            g[i]: 到i位置且不偷，取得的最大金额
    //2.状态转移方程：f[i]=g[i-1],g[i]=max(f[i-1],g[i-1])
    //3.填表顺序：从左往右
    int maxMoney(vector<int>& nums,int i,int j)
    {
        int len=j-i+1;
        if(len<=0)  return 0;
        vector<int> f(len);
        vector<int> g(len);
        f[0]=nums[i],g[0]=0;
        for(int k=i+1;k<=j;k++)
        {
            f[k-i]=nums[k]+g[k-i-1];
            g[k-i]=max(g[k-i-1],f[k-i-1]);
        }
        return max(f[len-1],g[len-1]);
    }
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==0)  return 0;
        return max(nums[0]+maxMoney(nums,2,n-2),maxMoney(nums,1,n-1));
    }
};